package binaryTree;

import java.util.ArrayList;
import java.util.List;

public class Class653 {


    //  CKG TODO 2023/4/5: 我的解决办法解决的问题是 bst中是否存在相邻两个节点 满足给定的目标值
    TreeNode pre;
    Boolean result=false;
    public boolean findTarget(TreeNode root, int k) {
        if (root==null){
            return false;
        }
        traverse(root,k);
        return  result;
    }

    public  void  traverse(TreeNode root,int k){
        if (root==null){
            return;
        }
        traverse(root.left,k);

        if (pre==null){
            pre=root;
        }
        else if (k==pre.val+root.val){
            result=true;
            return;
        }
        if (k<pre.val+root.val){
            return;
        }else {
            pre=root;
        }

        traverse(root.right,k);

    }


    class Solution {
        //创建一个可变长数组列表
        List<Integer> result=new ArrayList<Integer>();
        public boolean findTarget(TreeNode root, int k) {
            dfs(root);
            //双指针
            int left=0;
            int right=result.size()-1;
            while(left<right){
                if(result.get(left)+result.get(right)>k){
                    right--;
                }
                else if(result.get(left)+result.get(right)<k){
                    left++;
                }
                else{
                    return true;
                }

            }
            return false;

        }
        public void dfs(TreeNode root){
            if(root==null){
                return;
            }
            dfs(root.left);
            result.add(root.val);
            dfs(root.right);
        }
    }







    public static void main(String[] args) {
        TreeNode treeNode1 = new TreeNode(1);
        TreeNode treeNode2 = new TreeNode(2);
        TreeNode treeNode3 = new TreeNode(3);
        treeNode2.left=treeNode1;
        treeNode2.right=treeNode3;
        Class653 class653 = new Class653();
        System.out.println(class653.findTarget(treeNode2, 4));



    }


}
